package momo.multitree.structure;

import java.io.IOException;
import java.io.Reader;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.Vector;

import momo.multitree.visual.GraphVisualOutput;
import momo.multitree.visual.TreeRenderOutput;
import momo.multitree.visual.TreeVisualOutput;

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;


public class Tree extends Graph implements Cloneable
{
	private TreeVisualOutput visualTool;
	private Log log = LogFactory.getLog(Tree.class); 
	
	private Node root;
	

	/**
	 * maps a node to its parent
	 */
	private HashMap<Node, Node> parentMap = new LinkedHashMap<Node, Node>(); 
	
	private Tree() {
		throw new IllegalStateException("tree must have a root");
	}
	
	public Tree(Node root) {
		super();
		this.root = root;
		parentMap.put(root, null);
		visualTool = new TreeRenderOutput();
	}
	
	public Tree(Node root, Graph g) {
		super();
		this.root = root;
		parentMap.put(root, null);
		visualTool = new TreeRenderOutput();
		
		for (Node node : g.getNodes())
			this.add(node);
		
		LinkedList<Node> toVisit = new LinkedList<Node>();
		toVisit.add(root);
		
		while (!toVisit.isEmpty()) {
			Node visited = toVisit.pop();
			for (Edge edge : g.getEdgesOfNode(visited)) {
				if (!this.getEdges().contains(edge)) { // new edge, so one of the nodes is new to the graph
					this.add(edge, visited);
					toVisit.add(edge.nextNode(visited));
				}
			}
		}
	}
	
	public Tree(Reader in) throws Exception
	{
		super();
		visualTool = new TreeRenderOutput();
		
		int chr;
		StringBuffer buffer = new StringBuffer();
		while ((chr = in.read()) > -1) {
			buffer.append((char)chr);
		}
		in.close();
		
		//start processing
		HashMap<String, Node> mapNode = new HashMap<String, Node>(); 
		String lineBreak = System.getProperty("line.separator");
		String rawData = buffer.toString();
		
		StringTokenizer lineTokens = new StringTokenizer(rawData, lineBreak);
		
		int noOfNodes = Integer.parseInt(lineTokens.nextToken());
		
		Node[] nodes = new Node[noOfNodes];
		for(int i=0; i<noOfNodes; i++)
		{
			String lineOfNodeData = lineTokens.nextToken().trim();
			StringTokenizer nodeTokens = new StringTokenizer( lineOfNodeData, ", " );
			String id = nodeTokens.nextToken().trim();
			double workload = Double.parseDouble(nodeTokens.nextToken().trim());
			double stability = Double.parseDouble(nodeTokens.nextToken().trim());
			nodes[i] = new Node(id, workload, stability);
			mapNode.put(id, nodes[i]);
		}
		
		this.root = nodes[0];
		parentMap.put(root, null);
		
		int noOfEdges = Integer.parseInt(lineTokens.nextToken().trim());
		
		Edge[] edges = new Edge[noOfEdges];
		for(int i=0; i<noOfEdges; i++)
		{
			String lineOfEdgeData = lineTokens.nextToken().trim();
			StringTokenizer edgeTokens = new StringTokenizer( lineOfEdgeData, ", " );
			String edgeId = edgeTokens.nextToken().trim();
			Node headNode = mapNode.get(edgeTokens.nextToken().trim());
			Node tailNode = mapNode.get(edgeTokens.nextToken().trim());
			double latHT = Double.parseDouble(edgeTokens.nextToken().trim());
			double latTH = Double.parseDouble(edgeTokens.nextToken().trim());
			double costHT = Double.parseDouble(edgeTokens.nextToken().trim());
			double costTH = Double.parseDouble(edgeTokens.nextToken().trim());
			edges[i] = new Edge(edgeId, headNode, tailNode, costHT, costTH, latHT, latTH);
			this.add(edges[i]);
		}
	}
	
	public Tree clone() {
		Tree cloned = new Tree(this.root, this );   
		return cloned;
	}
	
	/**
	 * either edge.head or edge.tail must be in the tree
	 */
	public boolean add(Edge edge)
	{
		
		/*
		 * check if edge.nodeFrom in Tree
		 * [Fixme] jack->krz: Do we still need to check the above statement?
		 */
		
		//strict checking if new edge is connected to any of the current nodes
//		assert isEdgeConnected(edge);
		
		//check if theres cycle
		assert !hasCycle(edge);
		
//		Node parentNode = edge.getHeadNode();
//		if (!parentMap.containsKey(parentNode))
//			parentNode = edge.getTailNode();
//		if (!parentMap.containsKey(parentNode)) {
//			throw new IllegalStateException("No parent node for edge: "+edge);
//		}
//		
//		Node childNode = edge.nextNode(parentNode);
//		if (childNode == root) {
//			throw new IllegalStateException("child is root");
//		}
//	
		Node parent = null;
		Node child = null;
		
		Node n1 = edge.getHeadNode();
		Node n2 = edge.getTailNode();
		if (rootConnected(n1)) 
			parent = n1;
		else {
			if (!rootConnected(n2)) {
				throw new IllegalStateException("edge disconnected from the tree "+edge);
			}
			else		
				parent = n2;
		}
		child = edge.nextNode(parent);
		
		boolean success = super.add(edge);
		if (success) {
//			parentMap.put(edge.nextNode(parentNode), parentNode);
			restructureParentMap(parent, child);
		}
		
		return success;
	}
	
	
	public boolean rootConnected(Node n) {
		Node curr = n;
		while (curr != root) {
			if (!parentMap.containsKey(curr))
				return false;
			Node parent = parentMap.get(curr);
			if (parent == null)
				return false;
			curr = parent;
		}
		return true;
	}
		
	/**
	 * Problem:
	 * 1.) Node 1 -> (is parent of) Node 2 -> Node 3 -> Node 4
	 * 2.) Removal of edge (Node 2 -> Node 3)
	 * 3.) Add edge (Node 1 -> Node 4)
	 * 4.) The parent mapping of Node 3 -> Node 4 isn't Node 4 -> Node 3
	 * This method sets the new mapping and solves the above problem.
	 * @param newParent the new parent Node of the targeted child node
	 * @param child taget node for traversal to solve the parent mapping 
	 */
	private void restructureParentMap(Node newParent, Node child) {
		parentMap.put(child, newParent);
		
		if (getParent(root) != null) {
			throw new IllegalStateException("root has a parent");
		}
		
		Vector<Node> v = new Vector<Node>();
		v.add(child);
		
		while ( v.size() > 0 ) {
			Node curNode = v.remove(0);
			Node parentOfCurNode = parentMap.get(curNode);
			for ( Edge e : getEdgesOfNode(curNode) ) {
				Node nextNode = e.nextNode(curNode);
				if ( nextNode != parentOfCurNode ) {
					parentMap.put(nextNode, curNode);
					if (getParent(root) != null) {
						throw new IllegalStateException("root has a parent");
					}
					v.add(nextNode);
				}
			}
		}
		
	}
	
	public Node getParent(Node child) {
//		if (parentMap.containsKey(child))
//			return parentMap.get(child);
//		else
//			throw new IllegalArgumentException("Node "+child+" not found in parentMap");
		
		if ( !getNodes().contains(child) )
			throw new IllegalArgumentException("Node "+child+" not found in parentMap");
		return parentMap.get(child);
		
	}
	
//	public void checkParentMap() {
//		Collection<Node> nodes = getNodes();
//		for (Node n : nodes) {
//			Node parent = getParent(n);
//			if (n == root) {
//				if (parent != null) 
//					throw new IllegalStateException("the root has non-null parent mapping. current tree\n"+stringParentMap());
//			} else {
//				Edge e = getEdge(n, parent);
//				if (e == null) 
//					throw new IllegalStateException("node "+n+" parent: "+parent+" but edge is null. current tree\n"+stringParentMap());
//			}
//		}
//	}
	
//	public String stringParentMap() {
//		String out = "";
//		for ( Node child : parentMap.keySet() ) {
//			Node parent = parentMap.get(child);
//			if ( parent == null )
//				out += "child-id: " + child.getId() + ", parent-id: " + parent + "\n";
//			else
//				out += "child-id: " + child.getId() + ", parent-id: " + parent.getId() + "\n";
//		}
//		return out;		
//	}
	
	public Set<Node> getChildren(Node parent) {
		Set<Node> children = new LinkedHashSet<Node>();
		for (Edge edge : getEdgesOfNode(parent)) {
			Node suspectedChild = edge.nextNode(parent);
			if (getParent(suspectedChild) == parent)
				children.add(suspectedChild);
		}
		return children;
	}
	
	public Set<Node> getDescendants(Node parent) {
		Set<Node> descendants = new LinkedHashSet<Node>();
		Vector<Node> v = new Vector<Node>( getChildren(parent) );
		while ( v.size() > 0 ) {
			Node curParent = v.remove(0);
			descendants.add(curParent);
			v.addAll( getChildren(curParent) );
		}
		return descendants;
	}
	
	/**
	 * Adds edge with the specified parent (one of the ends of the edge)
	 * @param edge
	 * @param parent
	 * @return
	 */
	public boolean add(Edge edge, Node parent) {
		if ((!parent.equals(edge.getTailNode())) && (!parent.equals(edge.getHeadNode())))
			throw new IllegalArgumentException("Node: "+parent+" is not one of the nodes from the edge: "+edge);
		
		if (!parentMap.containsKey(parent))
			throw new IllegalStateException("node "+parent+" is not in parent graph");
		
		boolean success = super.add(edge);
		if (success) {
			parentMap.put(edge.nextNode(parent), parent);
		}
		return success;
	}
	
	/**
	 * it can break the tree into a forest, but we don't care here
	 */
	public boolean remove(Edge edge) {
		if (super.remove(edge)) {
			Node suspectedChild = edge.getHeadNode();
			if (parentMap.get(suspectedChild) != edge.getTailNode())
				suspectedChild = edge.getTailNode();
			if (parentMap.get(suspectedChild) != edge.nextNode(suspectedChild)) {
				throw new IllegalArgumentException("suspectedChild: "+suspectedChild.getId()+" parent is: "+parentMap.get(suspectedChild).getId()+" edge is: "+edge);
			}
			//assert parentMap.get(suspectedChild) == edge.getTailNode();
//			parentMap.put(suspectedChild, null);
			Node oldParent = parentMap.remove(suspectedChild);
			if (oldParent == null) {
				throw new IllegalStateException("couldn't remove parent mapping for "+suspectedChild);
			}
			
			return true;
		} 
		else
			return false; 
	}
		
	public boolean isEdgeConnected(Edge edge)
	{
		if ( getNoOfEdges() == 0 )
			return edge.contains(root, Edge.OBJECT);
		else
			return ( getNodes().contains(edge.getHeadNode()) || getNodes().contains(edge.getTailNode()) ); 
	}
	
	/**
	 * Checks if the existing tree with 'edge' added would result in a cycle
	 * Use DFS check - if bump and not parent = cycle
	 * @param edge
	 * @return
	 */
	public boolean hasCycle(Edge edge)
	{
		HashSet<Node> visited = new HashSet<Node>();
		
		Node parent = edge.getHeadNode();
		visited.add(parent);
		
		return hasCycle(visited, parent, edge.getTailNode());
	}
	
	/**
	 * Using DFS to check if it has cycles. This method is recursive.
	 * @param visited
	 * @param parent
	 * @param currNode
	 * @return
	 */
	private boolean hasCycle(HashSet<Node> visited, Node parent, Node currNode)
	{
		visited.add(currNode);
		
		Set<Edge> set = getEdgesOfNode(currNode);
		Iterator<Edge> iter = set.iterator();
		while ( iter.hasNext() )
		{
			Edge edge = iter.next();
			Node toNode = edge.nextNode(currNode);
			
//			System.out.println("Node To: " + toNode.getId());
			
			if ( !visited.contains(toNode) )
			{
				if ( hasCycle(visited, currNode, toNode) )
					return true;
			}else if ( toNode != parent )
				return true;
		}
		return false;
	}
	
	public double compDecentWeightedLatency()
	{
		double decentWeightedLatency = 0;
		for(Node curRoot:this.getNodes())
		{
			LatencyPair pairs = new LatencyPair();
			HashSet<Node> visited = new HashSet<Node>();
			Vector<Node> toVisit = new Vector<Node>();
			toVisit.add(curRoot);
			
			while (toVisit.size() > 0)
			{
				Node currNode = toVisit.remove(0);
				visited.add(currNode);
				
				Set<Edge> set = this.getEdgesOfNode(currNode);
				Iterator<Edge> iter = set.iterator();
				
				while ( iter.hasNext() )
				{
					Edge edge = iter.next();
					Node toNode = edge.nextNode(currNode);
					double currLat = edge.getLatency(currNode);
					
					if ( !visited.contains(toNode) )
					{
						//downstream link
						toVisit.add(toNode);
						double prevLat = pairs.getPair(root, currNode);
						double lat = prevLat + currLat;
						pairs.setPair(root, toNode, lat);
						pairs.setMaxLat(toNode, lat);
					}
				}
			}
			decentWeightedLatency += curRoot.getWorkloadRate() *  pairs.getMaxLat(curRoot);
		}//end of for loop
		return decentWeightedLatency;
	}
	
	public double compWeightedLatency()
	{
		//setup first
		LatencyPair pairs = new LatencyPair();
		HashSet<Node> visited = new HashSet<Node>();
		Vector<Node> toVisit = new Vector<Node>();
		
		toVisit.add(root);
		
		while ( toVisit.size() > 0 )
		{
			Node currNode = toVisit.remove(0);
			visited.add(currNode);
			
			Set<Edge> set = this.getEdgesOfNode(currNode);
			Iterator<Edge> iter = set.iterator();
			
			while ( iter.hasNext() )
			{
				Edge edge = iter.next();
				Node toNode = edge.nextNode(currNode);
				double currLat = edge.getLatency(currNode);
				
				if ( !visited.contains(toNode) )
				{
					//downstream link
					toVisit.add(toNode);
					double prevLat = pairs.getPair(root, currNode);
					double lat = prevLat + currLat;
					pairs.setPair(root, toNode, lat);
					pairs.setMaxLat(toNode, lat);
				}else
				{
					//upstream link
					double prevLat = pairs.getPair(toNode, root);
					pairs.setPair(currNode, root, prevLat + currLat);
				}
			}
		}
		//end of setup
		
		//starts to compute
		double weightedLat = 0;
		
		Set<Node> nodes = this.getNodes();
		Iterator<Node> iter = nodes.iterator();
		while(iter.hasNext())
		{
			Node currNode = iter.next();
//			weightedLat += ( currNode.getWorkloadRate()* ( pairs.getPair(currNode, root) + pairs.getMaxLat(currNode) ) );
			weightedLat += currNode.getWorkloadRate() *  pairs.getPair(currNode, root);
		}
		weightedLat += pairs.getMaxLat(root);
		
		return weightedLat;
	}
	
	
	private boolean ignoreStability = false;
	public void setIgnoreStability(boolean ignoreStability) {
		this.ignoreStability = ignoreStability;
	}
	
	public double compStability()
	{
		if (ignoreStability)
			return 1.0;
		
		double stability = 0;
		
		HashSet<Node> visited = new HashSet<Node>();
		Vector<Node> toVisit = new Vector<Node>();
		
		toVisit.add(root);
		
		while ( toVisit.size() > 0 )
		{
			Node currNode = toVisit.remove(0);
			visited.add(currNode);
			
			Set<Edge> set = this.getEdgesOfNode(currNode);
			Iterator<Edge> iter = set.iterator();
			
			int directChildren = 0;
			while ( iter.hasNext() )
			{
				Edge edge = iter.next();
				Node toNode = edge.nextNode(currNode);
				if ( !visited.contains(toNode) )
				{
					toVisit.add(toNode);
					directChildren ++;
				}
			}
			stability += ( directChildren * currNode.getStability() );
		}
		
		return stability;
	}
	
	public double compCost() {
		return compCost(true);
	}
	
	public double compCost(boolean substractLeafs)
	{
		NodePair pairs = new NodePair();
		double allCost = 0;
		double leafCost = 0;
		double toRootCost = 0;
		
		HashSet<Node> visited = new HashSet<Node>();
		Vector<Node> toVisit = new Vector<Node>();
		
		toVisit.add(root);
		
		while ( toVisit.size() > 0 )
		{
			Node currNode = toVisit.remove(0);
			visited.add(currNode);
			
			Set<Edge> set = this.getEdgesOfNode(currNode);
			Iterator<Edge> iter = set.iterator();
			
			while ( iter.hasNext() )
			{
				Edge edge = iter.next();
				Node toNode = edge.nextNode(currNode);
				double currCost = edge.getCost(currNode);
				
				if ( !visited.contains(toNode) )
				{
					//downstream link
					toVisit.add(toNode);
					
					allCost += currCost; //Sum of c(parent(v), v)
//					System.out.println("All Cost: " + allCost);
					
					//check if its a leaf
					if ( getEdgesOfNode(toNode).size() == 1 )
					{
						leafCost += (toNode.getWorkloadRate()* currCost);
//						System.out.println("leaf Cost: " + leafCost);
					}
				}else
				{
					//upstream link
					double prevCost = pairs.getPair(toNode, root);
					pairs.setPair(currNode, root, prevCost + currCost);
				}
			}
		}
		
		//starts to compute toRootCost
		Set<Node> nodes = this.getNodes();
		Iterator<Node> iter = nodes.iterator();
		while(iter.hasNext())
		{
			Node currNode = iter.next();
			toRootCost += ( currNode.getWorkloadRate()* pairs.getPair(currNode, root) );
//			System.out.println("toRootCost: " + toRootCost);
		}
		
		if (substractLeafs)
			return allCost - leafCost + toRootCost;
		else
			return allCost + toRootCost;
	}
	
	public String toString()
	{
		return "Root: " + root.toString() 
			+ "\n" + super.toString()
			+ "Latency: " + this.compWeightedLatency()
			+ "\nCost: " + this.compCost(false)
			+ "\nStability: " + this.compStability();
	}
	
	public Node getRoot() {
		return root;
	}
	
	public void changeRoot(Node root)
	{
		LinkedHashSet<Edge> visitedEdges = new LinkedHashSet<Edge>();
		
		parentMap.clear();
		this.root = root;
		parentMap.put(root, null);
		
		LinkedList<Node> toVisit = new LinkedList<Node>();
		toVisit.add(root);
		
		while (!toVisit.isEmpty()) {
			Node visited = toVisit.pop();
			for (Edge edge : this.getEdgesOfNode(visited)) {
				if (!visitedEdges.contains(edge))
				{
//					Node parentNode = edge.getHeadNode();
//					if (!parentMap.containsKey(parentNode))
//						parentNode = edge.getTailNode();
//					if (!parentMap.containsKey(parentNode))
//						throw new IllegalStateException("No parent node for edge: "+edge);
//					parentMap.put(edge.nextNode(parentNode), parentNode);
//					toVisit.add(edge.nextNode(visited));
					
					Node parentNode = visited;
					Node childNode = edge.nextNode(parentNode);
					parentMap.put(childNode, parentNode);
					toVisit.add(childNode);
					
					visitedEdges.add(edge);
					
				}
			}
		}
		if (parentMap.get(root) != null) {
			throw new IllegalStateException("after changeRoot the new root "+root+" has non-null parent "+parentMap.get(root));
		}
	}
	
	public void display()
	{
		Set<Node> keys = parentMap.keySet();
		for(Node key: keys)
			if ( key == root)
				log.info("Root: " + key.getId());
			else if (parentMap.get(key) == null )
				log.info("Leaf: " + key.getId());
			else
				log.info("Parent("+key.getId()+") = " + parentMap.get(key).getId());
	}

	public void setVisualTool(TreeVisualOutput visualTool)
	{
		this.visualTool = visualTool;
	}
	
	public void outputVisual(String filename) throws Exception
	{
		visualTool.setTree(this);
		visualTool.output(filename);
	}
		
}//end of class Tree
